//
//  Problem94.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/23.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 94. 二叉树的中序遍历
 给定一个二叉树的根节点 root ，返回它的 中序 遍历。

 示例 1：
    1
     \
      2
     /
    3

     输入：root = [1,null,2,3]
     输出：[1,3,2]
 
 示例 2：
     输入：root = []
     输出：[]
 示例 3：
     输入：root = [1]
     输出：[1]
 示例 4：
     输入：root = [1,2]
     输出：[2,1]
 示例 5：
     输入：root = [1,null,2]
     输出：[1,2]
 提示：
     树中节点数目在范围 [0, 100] 内
     -100 <= Node.val <= 100
 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 */
@objcMembers class Problem94: NSObject {
    func solution() {
        let root = TreeNode(2)
        root.left = TreeNode(3)
        root.left?.left = TreeNode(1)
        
        print(inorderTraversal_BFS2(root))
    }
    
    /*
     深度 递归
     */
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil {
            return []
        }
        if root?.left == nil, root?.right == nil {
            return [root!.val]
        }
        
        var list: [Int] = []
        list.append(contentsOf: inorderTraversal(root?.left))
        list.append(root!.val)
        list.append(contentsOf: inorderTraversal(root?.right))
        return list
    }
    
    /*
     广度 数组
     缺点 破坏树结构
     */
    func inorderTraversal_BFS(_ root: TreeNode?) -> [Int] {
        var nList: [Int] = []
        var list:[TreeNode?] = [root]
        while list.isEmpty == false {
            let node = list.removeFirst()
            if node == nil {
                continue
            }
            
            if node?.left == nil, node?.right == nil {
                nList.append(node!.val)
            } else  {
                list.insert(contentsOf: [node?.left, node, node?.right], at: 0)
                
                node?.left = nil
                node?.right = nil
            }
        }
        
        return nList
    }
    
    /*
     广度 数组
     不破坏树结构
     1: 从根开始，把左侧所有的节点放入数组list中
     2: 从list中取最后一个值，放入结果集中，然后判断是否有right
     3: 有right的话，执行步骤1
     */
    func inorderTraversal_BFS2(_ root: TreeNode?) -> [Int] {
        var nList: [Int] = []
        var list:[TreeNode?] = []
        
        // 1: 左侧节点放入数组中
        var node = root
        while node != nil || list.isEmpty == false {
            while node != nil {
                list.append(node)
                node = node?.left
            }
            
            node = list.removeLast()
            nList.append(node!.val)
            
            node = node?.right
        }
        
        return nList
    }
}
